package a10_动态规划;

import java.util.Arrays;

/**
 * <p>
 * a29_打家劫舍复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/18
 */
public class a29_打家劫舍复习3 {
    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 1, 1, 2}));
    }
    //dp[i][0]：第i间偷最大金额
    //dp[i][1]：第i间不偷最大金额

    //递推公式
    //dp[i][0]：第i间偷最大金额
    //i-1不偷：dp[i-1][1] + nums[i]
    //dp[i][1]：第i间不偷最大金额
    //i-1偷：dp[i-1][0]
    //i-1不偷：dp[i-1][1]

    //初始化
    //dp[0][0] = nums[0];
    //dp[0][1] = 0;
    public static int rob(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = 0;
        System.out.println(Arrays.toString(dp[0]));

        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i-1][1] + nums[i];
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]);
            System.out.println(Arrays.toString(dp[i]));
        }
        return Math.max(dp[dp.length-1][0],dp[dp.length-1][1]);
    }
}
